package cn.com.colasoft.dataStructure;

/**
 * [简单排序-插入排序]
 * 复杂度:O(N^2)
 * 原理: 利用一个全局临时变量存储当前取出来的需要用来比较与交换的值.
 * 插入排序是所有简单排序中相对比较好的一种
 * @author lizhitao
 * @date 2017/12/4
 */
public class InsertSort {

    /**
     * 排序,这里实现升序排序
     * @param arrays
     */
    public static void sort(long[] arrays) {
        long temp;
        int in;
        for (int out = 1; out < arrays.length; out++) {
            temp = arrays[out];
            in = out;
            while(in > 0 && arrays[in-1] >= temp) {
                arrays[in] = arrays[in-1];
                in--;
            }
            arrays[in] = temp;
        }
    }

    public static void main(String[] args) {
        long[] arrays = new long[]{5,6,7,4,3,1};
        sort(arrays);
        for (long item : arrays) {
            System.out.print(item + ",");
        }

    }
}
